#include <iostream>
#include <algorithm>
using namespace std;
/**
 * @brief ‌双指针交替扫描‌
初始化左右指针i=low和j=high，选取首个元素作为基准值(pivot)15
‌右指针先动‌：j向左遍历直到找到小于pivot的元素
‌左指针后动‌：i向右遍历直到找到大于pivot的元素
交换i和j位置的元素，重复此过程直到i≥j58
‌分区完成标志‌
当指针相遇时，将基准值与相遇点元素交换
最终i指针左侧元素≤pivot，右侧元素≥pivot17
 * 
 * @param a 
 * @param low 
 * @param high 
 * @return int 
 */
int partition(int*a , int low, int high)
{
    int pivot = a[low];  //选第一个元素作为基准
    int i= low, j = high;
    while (i < j)
    {
        while (i < j && a[j] >= pivot) j--;   //右指针向左移动，找到xiao于基准的数
        while (i < j && a[i] <= pivot) i++;   //左指针向右移动，找到da于基准的数
        if (i < j) swap(a[i], a[j]);
    }
    swap(a[low], a[i]);   
    return i;
}
void quick_sort(int*a , int low, int high)
{
    if (low < high){
        int pivot = partition(a, low, high);
        quick_sort(a, low, pivot - 1);
        quick_sort(a, pivot+1 , high);
    }
}
int findKth(int*a , int low, int high, int k){
    if  (low < high){
        int pivot = partition(a, low, high);
        if (pivot == k-1) return a[pivot];
        else if (pivot > k-1) return findKth(a, low, pivot - 1, k);
        else return findKth(a, pivot+1 , high, k);
    }
}
int main()
{
    int a[] = {10, 7, 8, 9, 1, 5};
    quick_sort(a, 0, 5);
    for(int i = 0; i < 5; i++){
        cout<<a[i]<<" ";
    }
    cout<<endl;
}